package br.puc.paa.graph.dijkstra;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

import br.puc.paa.datastructures.heap.fibonacci.FibonacciHeap;
import br.puc.paa.datastructures.heap.fibonacci.FibonacciHeapNode;
import br.puc.paa.graph.model.Aresta;
import br.puc.paa.graph.model.AvlNode;
import br.puc.paa.graph.model.AvlTree;
import br.puc.paa.graph.model.Grafo;
import br.puc.paa.graph.model.Vertice;
import br.puc.paa.util.TimeUtil;

public class Dijkstra {

	private Grafo grafo; // G(V,E)
	private Vertice verticeFonte; // s
	private EstruturaDeDados estruturaDeDadosDaDistancia;

	private List<Vertice> verticesAlcancados; // S
	private List<Vertice> verticesNaoAlcancados; // Ŝ
	private Map<Vertice, Vertice> predecessores; // pred
	private Integer[] vetorDeDistancias; // d, usando vetor
	private FibonacciHeap<Vertice> heapFibonacciDeVerticesPelaDistancia; // d, usando heap fibonacci
	private Object[] bucketsDeDistancias;// d, usando Buckets
	private AvlTree tree; // d, usando avl

	private Map<Object, Vertice> verticePeloElementoDaEstruturaDeDadosDaDistancia; // Mapa para auxiliar no resgate do vértice
	private Map<Vertice, Object> elementoDaEstruturaDeDadosDaDistanciaPeloVertice; // Mapa para auxiliar no resgate do elemento da estrutura de dados da distância que corresponde ao vértice

	private Integer custoMaximoPossivel;

	/**
	 * @param grafo, G(V,E)
	 * @param verticeFonte, s
	 * @param estruturaDeDadosDaDistancia
	 */
	public Dijkstra(Grafo grafo, Vertice verticeFonte, EstruturaDeDados estruturaDeDadosDaDistancia) {
		
		BigInteger tempoInicial = new BigInteger(String.valueOf(TimeUtil.getUserTime()));
		
		// Bloco de inicialização
		inicializarVariaveis(grafo, verticeFonte, estruturaDeDadosDaDistancia);

		// Bloco principal
		while (!verticesNaoAlcancados.isEmpty()) { // S ⊂ V

			// 1.1
			// Encontre v ∈ Ŝ t.q. d(v) = min d(w)
			Vertice verticeNaoAlcancadoComMenorDistancia = getVerticeNaoAlcancadoComMenorDistancia();

			// 1.2
			// S ← S U {v};
			verticesAlcancados.add(verticeNaoAlcancadoComMenorDistancia);
			// Ŝ ← Ŝ \ {v};
			verticesNaoAlcancados.remove(verticeNaoAlcancadoComMenorDistancia);

			// 1.3
			Integer distanciaDoVerticeRecetementeAlcancado = getDistancia(verticeNaoAlcancadoComMenorDistancia);

			// Se a menor distância do vertice não alcançado é igual a infinito,
			// o componente que o vértice fonte pertence já foi
			// totalmente escaneado, e os demais vértices do grafo não são mais
			// alcançáveis a partir do vértice fonte
			if (distanciaDoVerticeRecetementeAlcancado.equals(custoMaximoPossivel+1)) {
				break;
			}

			// Para todo w ∈ Γ+(v)
			for (Aresta aresta : verticeNaoAlcancadoComMenorDistancia.getArestasDeSaida()) {

				Integer custoAtualDoVerticeAdjacente = getDistancia(aresta.getDestino());
				Integer novoCustoDoVerticeAdjacente = distanciaDoVerticeRecetementeAlcancado + aresta.getCusto();

				// Se d(v) + lvw < d(w)
				if (novoCustoDoVerticeAdjacente < custoAtualDoVerticeAdjacente) {
					// d(w) ← d(v) + lvw
					diminuirDistancia(aresta.getDestino(), novoCustoDoVerticeAdjacente);
					// pred(w) ← v
					predecessores.put(aresta.getDestino(), verticeNaoAlcancadoComMenorDistancia);
				}

			}

		}
		
		BigInteger tempoDeExecucao = new BigInteger(String.valueOf(TimeUtil.getUserTime())).subtract(tempoInicial);
		
		System.out.println("Tempo gasto pelo algoritmo de Dijkstra: "+new BigDecimal(tempoDeExecucao).divide(new BigDecimal("10").pow(9))+" segundos");

	}
	
	private void inicializarVariaveis(Grafo grafo, Vertice verticeFonte, EstruturaDeDados estruturaDeDadosDaDistancia){
		
		this.verticeFonte = verticeFonte;
		this.grafo = grafo;
		this.estruturaDeDadosDaDistancia = estruturaDeDadosDaDistancia;

		verticesAlcancados = new ArrayList<Vertice>(); // S ← ∅
		verticesNaoAlcancados = new ArrayList<Vertice>(grafo.getVertices());
		predecessores = new HashMap<Vertice, Vertice>();
		
		// Custo do caminho máximo possível (No pior caso, soma dos custos de todas as arestas de saída)
		custoMaximoPossivel = 0;
		for (Vertice vertice : grafo.getVertices()) {
			for (Aresta aresta : vertice.getArestasDeSaida()) {
				custoMaximoPossivel += aresta.getCusto();
			}
		}
		
		construirEstruturaDaDistancia();

		for (Vertice vertice : grafo.getVertices()) { // d(i) ← +∞ ∀ i ∈ V
			if (vertice.equals(verticeFonte)) {
				inicializarDistancia(vertice, 0); // d(s) ← 0
				predecessores.put(verticeFonte, null); // pred(s) ← 0
			} else {
				//Como infinito é um valor inalcançável, custoMaximoPossivel + 1 pode ser considerado como infinito
				inicializarDistancia(vertice, custoMaximoPossivel+1); // d(i) ← +∞
			}
		}
		
	}

	private void construirEstruturaDaDistancia() {

		verticePeloElementoDaEstruturaDeDadosDaDistancia = new HashMap<Object, Vertice>();
		elementoDaEstruturaDeDadosDaDistanciaPeloVertice = new HashMap<Vertice, Object>();

		switch (estruturaDeDadosDaDistancia) {

		case VETOR: {
			vetorDeDistancias = new Integer[grafo.getVertices().size()];
			break;
		}
		case HEAP_FIBONACCI: {
			heapFibonacciDeVerticesPelaDistancia = new FibonacciHeap<Vertice>();
			break;
		}
		case ARVORE_BALANCEADA_DE_BUSCA: {
			tree = new AvlTree();
			break;
		}
		case BUCKETS: {
			bucketsDeDistancias = new Object[custoMaximoPossivel+2];
			break;
		}
		case ARVORE_ALFA: {
			break;
		}
		default:
			break;
		}
	}

	@SuppressWarnings("unchecked")
	private void inicializarDistancia(Vertice vertice, Integer distancia) {
		switch (estruturaDeDadosDaDistancia) {

		case VETOR:{ // CUSTO: O(N)
			int indiceDoVertice = grafo.getVertices().indexOf(vertice); //O(N)
			vetorDeDistancias[indiceDoVertice] = distancia; //O(1)
			break;
		}
		case HEAP_FIBONACCI:{ // CUSTO: O(1)
			FibonacciHeapNode<Vertice> fibonacciHeapNode = new FibonacciHeapNode<Vertice>(vertice); //O(1)
			verticePeloElementoDaEstruturaDeDadosDaDistancia.put(fibonacciHeapNode, vertice); //O(1)
			elementoDaEstruturaDeDadosDaDistanciaPeloVertice.put(vertice, fibonacciHeapNode); //O(1)
			heapFibonacciDeVerticesPelaDistancia.insert(fibonacciHeapNode, distancia); //O(1)
			break;
		}
		case ARVORE_BALANCEADA_DE_BUSCA:{
			tree.insert(distancia,vertice);
			break;
		}
		case BUCKETS:{ // CUSTO: O(1)

			if (bucketsDeDistancias[distancia] == null) {
				bucketsDeDistancias[distancia] = new LinkedList<Vertice>();
			}
			((LinkedList<Vertice>)bucketsDeDistancias[distancia]).add(vertice); //O(1)
			elementoDaEstruturaDeDadosDaDistanciaPeloVertice.put(vertice, distancia); //O(1)

			break;
		}
		case ARVORE_ALFA:{
			break;
		}
		default:
			break;

		}
	}

	@SuppressWarnings("unchecked")
	private void diminuirDistancia(Vertice vertice, Integer distancia) {
		switch (estruturaDeDadosDaDistancia) {

		case VETOR:{ // CUSTO: O(1)
			int indiceDoVertice = grafo.getVertices().indexOf(vertice);
			vetorDeDistancias[indiceDoVertice] = distancia;
			break;
		}
		case HEAP_FIBONACCI:{ // CUSTO: O(1), amortizado
			FibonacciHeapNode<Vertice> fibonacciHeapNode = (FibonacciHeapNode<Vertice>) elementoDaEstruturaDeDadosDaDistanciaPeloVertice.get(vertice);
			heapFibonacciDeVerticesPelaDistancia.decreaseKey(fibonacciHeapNode, distancia);
			break;
		}
		case ARVORE_BALANCEADA_DE_BUSCA:{
			AvlNode foundedAvlNode = tree.find(vertice);
			 if (foundedAvlNode != null) {
				 tree.remove(foundedAvlNode);
				 tree.insert(distancia,vertice);
			 }
			break;
		}
		case BUCKETS:{ // CUSTO: O(n)

			// Removendo vértice do bucket atual
			Integer distanciaAtual = getDistancia(vertice); // O(1)
			((LinkedList<Vertice>)bucketsDeDistancias[distanciaAtual]).remove(vertice); // O(1) + O(n), get + remove

			// Adicionando o vértice no novo bucket
			if (bucketsDeDistancias[distancia] == null) { // O(1)
				bucketsDeDistancias[distancia] = new LinkedList<Vertice>(); // O(1)
			}
			((LinkedList<Vertice>)bucketsDeDistancias[distancia]).add(vertice); // O(1) + O(1), get + add

			elementoDaEstruturaDeDadosDaDistanciaPeloVertice.put(vertice, distancia); // O(1)

			break;
		}
		case ARVORE_ALFA:{
			break;
		}
		default:
			break;

		}
	}

	@SuppressWarnings("unchecked")
	private Integer getDistancia(Vertice vertice) {
		switch (estruturaDeDadosDaDistancia) {

		case VETOR:{ // CUSTO: O(1)
			int indiceDoVertice = grafo.getVertices().indexOf(vertice);
			return vetorDeDistancias[indiceDoVertice];
		}
		case HEAP_FIBONACCI:{ // CUSTO: O(1), pode ser O(N) se o hash for mal implementado, mas estou otimista quanto ao hash do Vértice :)
			FibonacciHeapNode<Vertice> fibonacciHeapNode = (FibonacciHeapNode<Vertice>) elementoDaEstruturaDeDadosDaDistanciaPeloVertice.get(vertice);
			return (int) fibonacciHeapNode.getKey();
		}
		case ARVORE_BALANCEADA_DE_BUSCA:{
			AvlNode foundedAvlNode = tree.find(vertice);
			if (foundedAvlNode != null) return foundedAvlNode.element;
			return null;
		}
		case BUCKETS:{ // CUSTO: O(1), pode ser O(N) se o hash for mal implementado, mas estou otimista quanto ao hash do Vértice :)
			return (int) elementoDaEstruturaDeDadosDaDistanciaPeloVertice.get(vertice);
		}
		case ARVORE_ALFA:{
			return null;
		}
		default:
			return null;

		}
	}

	@SuppressWarnings("unchecked")
	private Vertice getVerticeNaoAlcancadoComMenorDistancia() {
		switch (estruturaDeDadosDaDistancia) {

		case VETOR: { // CUSTO: O(N)
			Integer menorDistancia = null;
			Vertice verticeComMenorDistancia = null;

			for (Vertice vertice : verticesNaoAlcancados) {
				Integer distancia = vetorDeDistancias[grafo.getVertices().indexOf(vertice)];
				if (menorDistancia == null || distancia < menorDistancia) {
					verticeComMenorDistancia = vertice;
					menorDistancia = distancia;
				}
			}

			return verticeComMenorDistancia;
		}
		case HEAP_FIBONACCI: { // CUSTO: O(Log N), amortizado
			FibonacciHeapNode<Vertice> minFibonacciHeapNode = heapFibonacciDeVerticesPelaDistancia.removeMin();
			return verticePeloElementoDaEstruturaDeDadosDaDistancia.get(minFibonacciHeapNode);
		}
		case ARVORE_BALANCEADA_DE_BUSCA: {
			Integer menorDistancia = null;
			Vertice verticeComMenorDistancia = null;
			for (Vertice vertice : verticesNaoAlcancados) {
				Integer distancia = tree.find(vertice).element;
				if (menorDistancia == null || distancia < menorDistancia) {
					verticeComMenorDistancia = vertice;
					menorDistancia = distancia;
				}
			}
			return verticeComMenorDistancia;
		}
		case BUCKETS: { //CUSTO: O(C), onde C é o caminho com maior custo possível

			Vertice verticeComMenorDistancia = null;

			// Já que o índice do vetor é igual a distancia associada aos vértices que pertencem à lista associdada ao dado índice, o vértice
			// com menor distância é igual a um vértice qualquer que pertencente à primeira lista encontrada ao percorrer o vetor de buckets,
			for (Object bucket : bucketsDeDistancias) {//O(C)
				
				LinkedList<Vertice> vertices = ((LinkedList<Vertice>)bucket);
				
				if (vertices != null && vertices.size() > 0) {
					verticeComMenorDistancia = vertices.getLast(); //O(1)
					vertices.removeLast();//O(1)
					break;
				}
			}

			return verticeComMenorDistancia;
		}
		case ARVORE_ALFA: {
			return null;
		}
		default:
			return null;
		}

	}

	public void imprimaMelhorCaminhoAte(Vertice verticeDestino) {

		Vertice verticePredecessor = predecessores.get(verticeDestino);

		if (verticePredecessor == null && !verticeDestino.equals(verticeFonte)) {
			System.out.println("Não é possível alcançar o vértice "+verticeDestino.getRotulo()+" a partir do vértice "+verticeFonte.getRotulo()+".");
		} else {
			StringBuilder stringBuilder = new StringBuilder();
			stringBuilder.insert(0, " -> " + verticeDestino.getRotulo());

			while (verticePredecessor != null) {
				stringBuilder.insert(0, " -> " + verticePredecessor.getRotulo());
				verticePredecessor = predecessores.get(verticePredecessor);
			}

			System.out.println("Caminho de "+verticeFonte.getRotulo()+" até "+verticeDestino.getRotulo()+" com custo mínimo: " + stringBuilder.toString().substring(4));
		}

	}

	public enum EstruturaDeDados {
		VETOR, HEAP_FIBONACCI, ARVORE_BALANCEADA_DE_BUSCA, BUCKETS, ARVORE_ALFA
	}

}
